#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,mod=111121;
long long n,m,a[N],l,r,qwq[N],top,z[N],lst[N],po,ans,w[N];
//vector<int>q[N];
//void dfs1(int i,int z,int lst)
//{
//	w[i]=z;
//	++top;
//	if(q[i].size>2) z=1;
//	for(int j=0;j<q[i].size();++j)
//	{
//		if(q[i][j]==lst) continue;
//	}
//}
long long ksm(long long i,long long j)
{
	i%=mod;
	long long ans1=1;
	while(j)
	{
		if(j%2==1) ans1=(ans1*i)%mod;
		i=(i*i)%mod;
		j/=2;
	} 
	return ans1;
}
int main()
{
	freopen("abstract.in","r",stdin);
	freopen("abstract.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i)
		cin>>a[i],ans+=a[i];
	for(int i=1;i<n;++i)
		cin>>l>>r;
//		q[l].push_back(r),q[r].push_back(l),++qwq[l],++qwq[r];
//	for(int j=1;j<=n;++j)
//		if(qwq[j]==1)
//			++po;
//	for(int i=1;i<=n&&1<po;++i)
//		if(qwq[i]==1)
//		{
//			dfs1(i,2,0);
//			--po;
//		}
	cout<<ksm(ans,ans-1);
	return 0;
} 
